from collections import Counter
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t) # 返回字母出现次数
        window = dict.fromkeys(need.keys(), 0) # 窗口内字母默认值为0
        valid, L, R = 0, 0, 0        
        ans= (-1, len(s))# 记录最小覆盖子串的起始索引及长度
        while R < len(s):
            c = s[R] # c 是将移入窗口的字符
            R += 1 # 右移窗口
            # 进行窗口内数据的一系列更新
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            # 判断左侧窗口是否要收缩
            while valid == len(need): # t 中所有字符已经被覆盖
                # 在这里更新最小覆盖子串
                ans = (L, R) if R - L < ans[1] - ans[0] else ans
                
                d = s[L] # d 是将移出窗口的字符
                L += 1 # 左移窗口

                # 进行窗口内数据的一系列更新
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        if ans[0] == -1:
            return ""
        # 返回最小覆盖子串
        return s[ans[0]:] if ans[1] == len(s) else s[ans[0]:ans[1]]

# 测试
s="ADOBECODEBANC"
t="ABC"
ans=Solution().minWindow(s,t)
print(t)
